
//
// 101207 - AH - (Galleriet, Augustin) Created.
// 101208a- AH - distance(Tree, Tree) and sumOfDistances(Tree).
// 101208b- AH - (Hector) sumOfDistances(int), mean(Tree), mean(int),
//               getIndexOf(Tree), getMeans() and getSmallAndDeep().
// 101209a- AH - TreeDistanceTable(Tree...).
// 101209b- AH - Fixed bug in getSmallestMeans() and made it public.
// 101209c- AH - TreeDistanceTable() and add(Tree).
// 101210a- AH - Now add(Tree) ignores duplicates.
// 101210b- AH - Missing java doc for getSmallAndDeep().
// 101210c- AH - Moved Mean as top level class and now passes this to its
//               constructor.
// 101210d- AH - Moved same(float, float) to new Util class.
// 101210e- AH - getWithDistanceLessOrEqual(int, float).
// 101210f- AH - (Hector) Fixed getSmallAndDeep return random among smallest
//               and deepest being equal.
// 101210g- AH - (Hector) Started getHtml(), TODO: finish.
// 110113 - AH - Allow mean to 0, something it can be.
//

package org.soekrat.engine.forest;


import java.io.CharArrayWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.soekrat.engine.util.Util.getRandom;
import static org.soekrat.engine.util.Util.same;

/**
 * <p>
 *   Table of distances between sub trees.
 * </p>
 * @author Arne Halvorsen (AH)
 * @author Laetitia Le Chatton (LLC)
 */
public final class TreeDistanceTable 
{
  private Tree m_root=null;
  
  private int[][] m_distances=null;
  
  private final List<Tree> m_trees=new ArrayList<Tree>();
  
  /**
   * <p>
   *   Constructs empty table, use
   *   {@link #add(Tree)} to add content and
   *   {@link #compute()} to complete table.
   * </p>
   */
  public TreeDistanceTable(){}

  /**
   * <p>
   *   Constructor.
   * </p>
   * @param trees {@link Tree}s to find distances between.
   */
  public TreeDistanceTable(Tree... trees){ this(Arrays.asList(trees)); }
  
  /**
   * <p>
   *   Constructor.
   * </p>
   * @param trees {@link Tree}s to find distances between.
   */
  public TreeDistanceTable(List<Tree> trees)
  { 
    if (trees==null)
    {
      throw new NullPointerException("trees");
    }
    
    int n=trees.size();
    
    if (n==0) 
    {
      m_root=null;
      return; 
    }
    
    Tree root=null;
    
    for (int i=0; i<n; i++)
    {
      Tree curr=trees.get(i);
      if (i==0)
      {
        root=curr.getRoot();
      }
      else
      {
        Tree r=curr.getRoot();
        if (r!=root)
        {
          throw new IllegalArgumentException("not of same tree");
        }
      }
      
      m_trees.add(curr);
    }
    
    m_root=root;
    
    compute();
  }
  
  /**
   * <p>
   *   Gets root table has been computed for.
   * </p>
   * @return Root or {@code null} if table is empty.
   */
  public Tree getRoot(){ return m_root; }
  
  /**
   * <p>
   *   Used to add 
   *   {@link Tree}s to table when constructed with
   *   {@link #TreeDistanceTable()}.
   * </p>
   * @param tree {@code Tree} to add.
   * @return {@code this}.
   * @throws IllegalArgumentException If {@code tree} is not first and does not
   *         belong to same tree as previous added.
   * @throws IllegalStateException If distances has been computed using
   *         {@link #compute()}, that marks the table complete.
   * @see #TreeDistanceTable()
   * @see #compute()
   */
  public TreeDistanceTable add(Tree tree)
  {
    if (tree==null)
    {
      throw new NullPointerException("tree");
    }
    
    if (m_distances!=null)
    {
      throw new IllegalStateException(
        "distances been computed, does not accepts more trees");
    }
    
    Tree root=tree.getRoot();
    if (m_root==null)
    {
      m_root=root;
    }
    else if (m_root!=root)
    {
      throw new IllegalArgumentException(
        "tree not in same tree as other in table");
    }
    
    if (!m_trees.contains(tree)) m_trees.add(tree);
    
    return this;
  }
  
  /**
   * <p>
   *   Invoked by clients when used 
   *   {@link #TreeDistanceTable()} and
   *   {@link #add(Tree)} to create table.
   * </p>
   * <p>
   *   Computes distances and makes the table complete, no more
   *   {@link Tree}s can be added.
   * </p>
   * @see #TreeDistanceTable()
   * @see #add(Tree)
   */
  public void compute()
  {
    if (m_distances!=null)
    {
      throw new NullPointerException("distances has been computed");
    }
    
    int n=m_trees.size();
    
    m_distances=new int[n][n];
    
    for (int i=0; i<n; i++)
    {
      Tree ti=m_trees.get(i);
      for (int j=0; j<n; j++)
      {
        if (i!=j)
        {
          Tree tj=m_trees.get(j);
          int d=ti.distance(tj);
          m_distances[i][j]=d;
        }
      }
    }
  }
  
  /**
   * <p>
   *   Gets distance between two 
   *   {@link Tree}s in the table.
   * </p>
   * @param t0 First tree.
   * @param t1 Second tree.
   * @return Distance.
   * @throws IllegalArgumentException If {@code t0} or {@code t1} not in table.
   */
  public int distance(Tree t0, Tree t1)
  {
    if (t0==null)
    {
      throw new NullPointerException("t0");
    }
    if (t1==null)
    {
      throw new NullPointerException("t1");
    }
    
    if (m_distances==null) compute();
    
    int t0idx=getIndexOf(t0);
    if (t0idx==-1)
    {
      throw new IllegalArgumentException("t0 not in table");
    }
    
    if (t0==t1) return 0;
    
    int t1idx=getIndexOf(t1);
    if (t1idx==-1)
    {
      throw new IllegalArgumentException("t1 not in table");
    }
    
    return m_distances[t0idx][t1idx];
  }

  /**
   * <p>
   *   Gets number of 
   *   {@link Tree}s in table.
   * </p>
   * @return Count.
   */
  public int size(){ return m_trees.size(); }
  
  /**
   * <p>
   *   Gets sum of distances given 
   *   {@link Tree} in table has with other
   *   {@link Tree}s in table. 
   * </p>
   * @param t {@code Tree}.
   * @return Sum of distances.
   * @throws IllegalArgumentException If {@code tree} is not in table.
   */
  public int sumOfDistances(Tree t)
  {
    if (t==null)
    {
      throw new NullPointerException("t");
    }
    
    int idx=getIndexOf(t);
    if (idx==-1)
    {
      throw new IllegalArgumentException("t1 not in table");
    }
    
    return sumOfDistances(idx);
  }
  
  /**
   * <p>
   *   Gets sum of distances given 
   *   {@link Tree} in table has with other
   *   {@link Tree}s in table. 
   * </p>
   * @param idx Index of 
   *            {@link Tree} to get sum for.
   * @return Sum of distances.
   * @throws IndexOutOfBoundsException If {@code idx<0 || idx>=size()}
   */
  public int sumOfDistances(int idx)
  {
    if (m_distances==null) compute();
    
    int[] ds=m_distances[idx];
    int n=ds.length;
    int retVal=0;
    for (int i=0; i<n; i++) if (i!=idx) retVal+=ds[i];
    return retVal;
  }
   
  /**
   * <p>
   *   Gets the mean of the distances a given 
   *   {@link Tree} in table has with other
   *   {@code Tree}s in the table.
   * </p>
   * @param tree {@code Tree}.
   * @return Mean.
   * @throws IllegalArgumentException If {@code tree} is not in table. 
   */
  public float mean(Tree tree)
  {
    int n=size();
    if (n<2) return 0.0f;
    int sum=sumOfDistances(tree);
    return ((float)sum)/(float)(size()-1);
  }
  
  /**
   * <p>
   *   Gets the mean of the distances a given 
   *   {@link Tree} in table has with other
   *   {@code Tree}s in the table.
   * </p>
   * @param idx Index 
   *            {@code Tree} to find mean for.
   * @return Mean.
   * @throws IllegalArgumentException If {@code tree} is not in table. 
   */
  public float mean(int idx)
  {
    int n=size();
    if (n<2) return 0.0f;
    int sum=sumOfDistances(idx);
    return ((float)sum)/(float)(size()-1);
  }
  
  /**
   * <p>
   *   Gets index of given
   *   {@link Tree} in table.
   * </p>
   * @param t {@link Tree} to get index of.
   * @return Index or {@code -1} if not found.
   */
  public int getIndexOf(Tree t){ return m_trees.indexOf(t); }
  
  /**
   * <p>
   *   Finds the means of the distances to the
   *   {@link Tree}s in the table.
   * </p>
   * @return {@link Mean} sorted on means.
   */
  public Mean[] getMeans()
  {
    int n=size();
    Mean[] retVal=new Mean[n];
    for (int i=0; i<n; i++) 
      retVal[i]=new Mean(this, m_trees.get(i), i, mean(i));
    Arrays.sort(retVal);
    return retVal;
  }
  
  /**
   * <p>
   *   Finds the smallest means of the distances to the
   *   {@link Tree}s in the table. 
   * </p>
   * @return {@link Mean} with smallest and equal means.
   */
  public Mean[] getSmallestMeans()
  {
    Mean[] means=getMeans();
   
    int n=means.length;
    if (n==0) return Mean.EMPTY_ARRAY;
    
    List<Mean> found=new ArrayList<Mean>();
    float min=Float.MAX_VALUE;
    
    for (int i=0; i<n; i++)
    {
      Mean curr=means[i];
      if (curr.mean<min || same(curr.mean, min))
      {
        found.add(curr);
        min=curr.mean;
      }
      else
      {
        return found.toArray(Mean.EMPTY_ARRAY);
      }
    }
    
    return found.toArray(Mean.EMPTY_ARRAY);
  }
  
  /**
   * <p>
   *   Gets the
   *   {@link Mean} that represents the
   *   {@link Tree} with the lowest mean and longest path to root.
   * </p>
   * @return Found or {@code null} if is empty.
   */
  public Mean getSmallAndDeep()
  {
    Mean[] means=getSmallestMeans();
    
    int n=means.length;
    switch (n)
    {
      case 0 : return null;
      
      case 1 : return means[0];
      
      default :
      {
        int maxDepth=getMaxDepth(means);
        List<Mean> found=new ArrayList<Mean>();
        for (int i=0; i<n; i++)
        {
          Mean curr=means[i];
          int depth=curr.tree.depth();
          if (maxDepth==depth) found.add(curr);
        }
        
        return getRandom(found);
      }
    }
  }
  
  private static int getMaxDepth(Mean[] means)
  {
    int max=-1;
    for (Mean mean : means) 
    {
      int d=mean.tree.depth();
      if (d>max) max=d;
    }
    return max;
  }
  
  /**
   * <p>
   *   Gets the 
   *   {@link Tree}s with distances less or equal to given distance from
   *   {@code Tree} with given index.
   * </p>
   * <p>
   *   The 
   *   {@code Tree} with index {@code idx} is always included.
   * </p>
   * @param idx Index of 
   *            {@code Tree} to take distances from.
   * @param d   Distance to be less or equal to.
   * @return Found.
   * @throws IndexOutOfBoundsException If {@code idx<0 || idx>=size()}.
   */
  public List<Tree> getWithDistanceLessOrEqual(int idx, float d)
  {
    List<Tree> retVal=new ArrayList<Tree>();
    
    retVal.add(m_trees.get(idx));
    
    int[] distances=m_distances[idx];
    int n=size();
    for (int i=0; i<n; i++)
    {
      if (i!=idx)
      {
        float currd=(float)distances[i];
        if (currd<d || same(currd, d)) retVal.add(m_trees.get(i));
      }
    }
    
    return retVal;
  }
  
  @Override
  public String toString() 
  {
    if (m_distances==null) compute();
    
    CharArrayWriter caw=new CharArrayWriter();
    PrintWriter pw=new PrintWriter(caw);
    
    StringBuilder sb=new StringBuilder();
    
    int n=m_trees.size();
    for (int i=0; i<n; i++)
    {
      sb.setLength(0);
      Tree ti=m_trees.get(i);
      sb.append(ti.getName()).append(" : ");
      
      for (int j=0; j<n; j++)
      {
        Tree tj=m_trees.get(j);
        
        if (i!=j)
        {
          sb.append(tj.getName()).append("(").append(m_distances[i][j])
            .append(")");
        }            
      }
      pw.println(sb);
    }
    
    pw.flush();
    return caw.toString();
  }
  
  // TODO Finish this shit.
  public String getHtmlTable()
  {
    StringBuilder sb=new StringBuilder();
    
    sb.append("<html>");
      sb.append("<table border='1'>");
      
        int n=size();
        
        sb.append("<tr>");
        for (int i=0; i<n; i++)
        {
          Tree curr=m_trees.get(i);
          sb.append("<td>").append(curr.getName()).append("</td>");
        }
        sb.append("</tr>");
        
        for (int i=0; i<n; i++)
        {
          sb.append("<tr>");
          for (int j=0; j<n; j++)
          {
            
          }
          sb.append("</tr>");
        }
        
      sb.append("</table>");
    sb.append("</html>");
    
    return sb.toString();
  }
  
}
